package com.wenhao.leetcode.medium;

/**
 * 题目：https://leetcode-cn.com/problems/minimum-path-sum/
 * 最小路径和
 *
 * @author Wenhao Tong
 * @Description
 * @create 2021-07-01 12:23
 */
public class LeetCode64 {

    public static void main(String[] args) {
        LeetCode64 leetCode64 = new LeetCode64();
        int[][] matrix = new int[][]{
                {1,3,1},
                {1,5,6},
                {9,2,1}
        };
        int res = leetCode64.minPathSum2(matrix);
        System.out.println(res);
    }

    int result = Integer.MAX_VALUE;

    public int minPathSum(int[][] grid) {
        dfs(0,0,0,grid);
        return result;
    }

    /**
     *
     * @param grid
     * @return
     */
    public int minPathSum2(int[][] grid) {
        int[][] sums = new int[grid.length][grid[0].length];
        sums[0][0] = grid[0][0];
        for (int i = 1;i < grid.length;i++) {
            sums[i][0] = sums[i - 1][0] + grid[i][0];
        }
        for (int i = 1;i < grid[0].length;i++) {
            sums[0][i] = sums[0][i - 1] + grid[0][i];
        }

        for (int i = 1;i < grid.length;i++) {
            for (int j = 1;j < grid[i].length;j++) {
                sums[i][j] = (sums[i - 1][j] < sums[i][j - 1] ? sums[i - 1][j] : sums[i][j - 1]) + grid[i][j];
            }
        }
        return sums[sums.length - 1][sums[0].length - 1];
    }

    /**
     * dfs的效率实在是太低啦！指数级的
     * @param x
     * @param y
     * @param sum
     * @param grid
     */
    private void dfs (int x,int y,int sum,int[][] grid) {
        sum = sum + grid[x][y];
        if (sum >= result) {
            return;
        }
        if (x == grid.length - 1 && y == grid[0] .length - 1) {
            result = result < sum ? result : sum;
            return;
        }
        if (x + 1 < grid.length) {
            dfs(x + 1,y,sum,grid);
        }
        if (y + 1 < grid[0].length) {
            dfs(x,y + 1,sum,grid);
        }
    }


}
